package com.irenty.interview.datastructures;

/**
 * 1.3 Design an algorithm and write code to remove the duplicate characters in
 * a string without using any additional buffer. NOTE: One or two additional
 * variables are fine. An extra copy of the array is not. FOLLOW UP Write the
 * test cases for this method.
 * 
 * @author irenty
 * 
 */
public class RemoveDuplicateCharacters {

	/**
	 * O(n2)
	 * 
	 * @param input
	 * @return
	 */
	public static char[] remove1(char[] input) {
		if (input == null)
			return null;
		if (input.length < 2)
			return input;

		char[] output = input;
		int after = 1;
		// traverse all chars
		for (int current = 0; current < input.length - 1; current++) {
			char currentChar = input[current];

			// skip duplicate letters
			int i = after;
			while (i < input.length) {
				if (currentChar != input[i]) {
					break;
				} else {
					i++;
				}
			}

			// i points to the first not duplicate
			if (i < input.length) {
				input[current + 1] = input[i];
				after = i + 1;
			} else {
				// return shorter string
				if (current < input.length - 1) {
					output = new char[current + 1];
					for (int j = 0; j < current + 1; j++) {
						output[j] = input[j];
					}
				}
				break;
			}

		}
		return output;
	}

	// O(n)
	public static char[] remove2(char[] input) {
		if (input == null)
			return null;
		if (input.length < 2)
			return input;

		char[] output = input;
		int current = 0;
		// traverse all chars
		for (int next = 1; next < input.length; next++) {
			char currentChar = input[current];

			// skip duplicate letters
			if (currentChar == input[next]) {
				continue;
			}

			// next points to the first not duplicate
			input[current + 1] = input[next];

			current++;
		}
		// return shorter string if needed
		if (current < input.length - 1) {
			output = new char[current + 1];
			for (int j = 0; j < current + 1; j++) {
				output[j] = input[j];
			}
		}

		return output;
	}

}
